/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-09 11:00 星期四
 * @motto the harder, the luckier。
 */

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class _19_RemoveNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
    public static void main(String[] args) {
        // 创建一个链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 打印原始链表
        System.out.println("原始链表：");
        printList(head);

        // 创建 _19_RemoveNthFromEnd 对象
        _19_RemoveNthFromEnd remover = new _19_RemoveNthFromEnd();

        // 移除倒数第二个节点
        int n = 2;
        ListNode newHead = remover.removeNthFromEnd(head, n);

        // 打印移除后的链表
        System.out.println("\n移除倒数第 " + n + " 个节点后的链表：");
        printList(newHead);
    }

    // 辅助方法：打印链表
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

}
